package com.yinxin.wudasuanfa.dongtaiguihua;


/**
 * @author yinxin
 * @version 1.0
 * @Description: 分支限界法
 * 也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。
 * 回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，
 * 或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
 * @date 2022/5/710:40
 */
public class Exercise7 {
    //问题：假设N=4件商品，分别用A、B、C、D表示。每件商品的重量分别为3kg，2kg，5kg和4kg，对应的价值分别为66元，40元，95元和40元。
    //现在有一个背包，可以容纳的总重量为9kg，问：如何挑选商品，使得背包里的商品的总价值最大。
    private static int NUM = 0;
    private int weight_MAx;

    Exercise7(int weight_MAx, int value[], int weight[]) {
        this.weight_MAx = weight_MAx;//先获取到质量
        copy(value, weight);//赋值排序同时进行
    }

    private Weight weights[];

    private class Weight {
        int value;//价值
        int weight;//质量
        double p;//性价比
        int num;//编号

        Weight(int value, int weight) {
            num = ++NUM;
            this.value = value;
            this.weight = weight;
            p = value / weight;
        }
    }

    //定义优先队列中的元素节点
    private class Element {
        //优先队列中的元素
        boolean isOne[] = new boolean[weights.length];//对应物品数组 是否被录用
        //最大的性价比乘总重量得出来的价值
        double ub = weight_MAx * weights[0].p;
        //最大初始价值
        int v = 0;//当前价值
        int w = 0;//当前质量
        int n = 0;//所处树的层数
        public Element() {
        }
        private Element(boolean isOne[], double ub, int v, int w, int n) {
            this.isOne = isOne;
            this.ub = ub;
            this.v = v;
            this.w = w;
            this.n = n;
        }
        Element newElement(boolean isOne) {//下一层
            if (n + 1 == weights.length) {
                n++;
                return null;
            }
            double ub;
            int v = this.v, w = this.w, n = this.n;
            if (isOne) {
                v += weights[n].value;
                w += weights[n].weight;
            }
            this.isOne[n] = isOne;
            if (++n < weights.length){
                ub = (weight_MAx - w) * weights[n].p + v;
            } else {
                ub = w;
            }
            return new Element(this.isOne, ub, v, w, n);
        }
    }

    public int[] F() {
        int mubiao[] = new int[weights.length];
        Element e = new Element();//开始
        Element E[] = new Element[20];//将优先队列 转化为栈 栈中最多可能性为：层数
        int top = -1;
        E[++top] = e;//进栈操作
        System.out.println("进栈操作");
        print(e);
        while (true) {        //当遍历到底时结束
            Element temp = E[top--];//将栈弹栈
            System.out.println("出栈操作");
            print(temp);
            Element nweElement1 = temp.newElement(false);
            Element nweElement2 = null;
            if (temp.n == weights.length) {
                System.out.println("遍历结束");
                for (int i = 0; i < mubiao.length; i++) {
                    if (temp.isOne[i]) {
                        mubiao[i] = weights[i].num;
                    }
                }
                return mubiao;
            }
            if ((weight_MAx - temp.w) >= weights[temp.n].weight) {
                nweElement2 = temp.newElement(true);
            }
            if (nweElement2 == null) {//优先左边
                E[++top] = nweElement1;
                System.out.println("进栈操作");
                print(nweElement1);
            } else if (nweElement1.ub <= nweElement2.ub) {
                E[++top] = nweElement1;
                E[++top] = nweElement2;
                System.out.println("进栈操作");
                print(nweElement1);
                System.out.println("进栈操作");
                print(nweElement2);
            } else {
                E[++top] = nweElement2;
                E[++top] = nweElement1;
                System.out.println("进栈操作");
                print(nweElement2);
                System.out.println("进栈操作");
                print(nweElement1);
            }
        }
    }

    private void copy(int V[], int W[]) {
        weights = new Weight[V.length];
        for (int i = 0; i < W.length; i++) {
            weights[i] = new Weight(V[i], W[i]);
            int key = i;
            Weight value = weights[i];

            while (key > 0 && weights[key - 1].p < value.p) {
                weights[key] = weights[key - 1];
                key--;
            }

            weights[key] = value;
        }
    }

    private void print(Element e) {
        if (e == null) {
            return;
        }
        System.out.println("操作物品的所处树的层数：" + e.n + " 该层物品是否装：入" + e.isOne[e.n] + "在该层时的价值：" + e.v + "在该层时的质量：" + e.w + "预测最大价值：" + e.ub);
    }
}

class Test {
    public static void main(String[] args) {
        int value[] = {12, 40, 42, 25};//价值
        int weight[] = {3, 4, 7, 5};//质量
        System.out.println("背包信息");
        for (int i = 0; i < value.length; i++) {
            System.out.println("编号：" + (i + 1) + "质量" + weight[i] + "价值" + value[i]);
        }
        int allWeight = 10;//背包总重
        // 建立执行表，建立后公共的Weight weights[]是建立后的产品表
        Exercise7 e = new Exercise7(allWeight, value, weight);
        int mubioa[] = e.F();
        System.out.print("背包录用编号：");
        for (int i : mubioa) {
            if (i != 0){
                System.out.print(i + "  ");
            }
        }
    }
}
